/**
 * Copyright (c) 2018-2022, NXOS Development Team
 * SPDX-License-Identifier: Apache-2.0
 * 
 * Contains: simple memory alloctor.
 *          This code from minix.
 * 
 * Change Logs:
 * Date           Author            Notes
 * 2022-05-23     JasonHu           Init
 */

#undef	 SLOWDEBUG	/* some extra test loops (requires DEBUG) */

#include <nxos/mman.h>
#include <nxos/utils.h>
#include <nxos/assert.h>

#define	ptrint		long

#define BRKSIZE		4096

#define	PTRSIZE		((int) sizeof(void *))
#define Align(x,a)	(((x) + (a - 1)) & ~(a - 1))
#define NextSlot(p)	(* (void **) ((p) - PTRSIZE))
#define NextFree(p)	(* (void **) (p))

/*
 * A short explanation of the data structure and algorithms.
 * An area returned by NX_MemAlloc() is called a slot. Each slot
 * contains the number of bytes requested, but preceeded by
 * an extra pointer to the next the slot in memory.
 * '_bottom' and '_top' point to the first/last slot.
 * More memory is asked for using NX_PosixBrk() and appended to top.
 * The list of NX_MemFree slots is maintained to keep NX_MemAlloc() fast.
 * '_empty' points the the first NX_MemFree slot. Free slots are
 * linked together by a pointer at the start of the
 * user visable part, so just after the next-slot pointer.
 * Free slots are merged together by NX_MemFree().
 */
NX_PRIVATE void *_bottom, *_top, *_empty;

NX_PRIVATE int Grow(NX_Size len)
{
    char *p;

    NX_ASSERT(NextSlot((char *)_top) == 0);
    if ((char *) _top + len < (char *) _top
        || (p = (char *)Align((ptrint)_top + len, BRKSIZE)) < (char *) _top 
        || NX_PosixBrk(p) != 0)
    {
        return(0);
    }
    NextSlot((char *)_top) = p;
    NextSlot(p) = 0;
    NX_MemFree(_top);
    _top = p;
    return 1;
}

void * NX_MemAlloc(NX_Size size)
{
    char *prev, *p, *next, *new;
    unsigned len, ntries;

    if (size == 0)
    {
        return NX_NULL;
    }
    for (ntries = 0; ntries < 2; ntries++)
    {
        if ((len = Align(size, PTRSIZE) + PTRSIZE) < 2 * PTRSIZE)
        {
            return NX_NULL;
        }
        if (_bottom == 0)
        {
            if ((p = NX_PosixSbrk(2 * PTRSIZE)) == (char *) -1)
            {
                return NX_NULL;
            }
            p = (char *) Align((ptrint)p, PTRSIZE);
            p += PTRSIZE;
            _top = _bottom = p;
            NextSlot(p) = 0;
        }
    #ifdef SLOWDEBUG
        for (p = _bottom; (next = NextSlot(p)) != 0; p = next)
        {
            NX_ASSERT(next > p);
        }
        NX_ASSERT(p == _top);
    #endif
        for (prev = 0, p = _empty; p != 0; prev = p, p = NextFree(p))
        {
            next = NextSlot(p);
            new = p + len;	/* easily overflows!! */
            if (new > next || new <= p)
            {
                continue;		/* too small */
            }
            if (new + PTRSIZE < next)
            {	/* too big, so split */
                /* + PTRSIZE avoids tiny slots on NX_MemFree list */
                NextSlot(new) = next;
                NextSlot(p) = new;
                NextFree(new) = NextFree(p);
                NextFree(p) = new;
            }
            if (prev)
            {
                NextFree(prev) = NextFree(p);
            }
            else
            {
                _empty = NextFree(p);
            }
            /* clear data */
            NX_MemSet(p, 0, size);
            return p;
        }
        if (Grow(len) == 0)
        {
            break;
        }
    }
    NX_ASSERT(ntries != 2);
    return NX_NULL;
}

void *
NX_MemReAlloc(void *oldp, NX_Size size)
{
    char *prev, *p, *next, *new;
    char *old = oldp;
    NX_Size len, n;

    if (!old)
    {
        return NX_MemAlloc(size);
    }
    else if (!size)
    {
        NX_MemFree(oldp);
        return NX_NULL;
    }
    len = Align(size, PTRSIZE) + PTRSIZE;
    next = NextSlot(old);
    n = (int)(next - old);			/* old length */
    /*
    * extend old if there is any NX_MemFree space just behind it
    */
    for (prev = 0, p = _empty; p != 0; prev = p, p = NextFree(p))
    {
        if (p > next)
        {
            break;
        }
        if (p == next)
        {	/* 'next' is a NX_MemFree slot: merge */
            NextSlot(old) = NextSlot(p);
            if (prev)
            {
                NextFree(prev) = NextFree(p);
            }
            else
            {
                _empty = NextFree(p);
            }
            next = NextSlot(old);
            break;
        }
    }
    new = old + len;
    /*
    * Can we use the old, possibly extended slot?
    */
    if (new <= next && new >= old)
    {		/* it does fit */
        if (new + PTRSIZE < next)
        {		/* too big, so split */
            /* + PTRSIZE avoids tiny slots on NX_MemFree list */
            NextSlot(new) = next;
            NextSlot(old) = new;
            NX_MemFree(new);
        }
        return old;
    }
    if ((new = NX_MemAlloc(size)) == NX_NULL)
    {
        return NX_NULL;
    }		/* it didn't fit */
    NX_MemCopy(new, old, n);				/* n < size */
    NX_MemFree(old);
    return new;
}

void *
NX_MemAlignedAlloc(NX_Size alignment, NX_Size size)
{
    void *raw_ptr, *new;

    /* alignment must be the power of 2. */
    if ((alignment & -alignment) != alignment)
    {
        return NX_NULL;
    }

    if (alignment <= PTRSIZE)
    {
        return NX_MemAlloc(size);
    }

    if (!(raw_ptr = NX_MemAlloc(size + alignment - PTRSIZE)))
    {
		return NX_NULL;
    }

    new = (void *)Align((NX_Size)raw_ptr, alignment);
    if (new == raw_ptr)
    {
        return raw_ptr;
    }

    /* NX_ASSERT(new - raw_ptr >= PTRSIZE); */
    /* split into 2 slots, then free the raw_ptr. */
    NextSlot(new) = NextSlot(raw_ptr);
    NextSlot(raw_ptr) = new;
    NX_MemFree(raw_ptr);
    return new;
}

void NX_MemFree(void *ptr)
{
    char *prev, *next;
    char *p = ptr;

    if (!p)
    {
        return;
    }

    NX_ASSERT((char *)NextSlot(p) > p);
    for (prev = 0, next = _empty; next != 0; prev = next, next = NextFree(next))
    {
        if (p < next)
        {
            break;
        }
    }
    NextFree(p) = next;
    if (prev)
    {
        NextFree(prev) = p;
    }
    else
    {
        _empty = p;
    }
    if (next)
    {
        NX_ASSERT((char *)NextSlot(p) <= next);
        if (NextSlot(p) == next)
        {		/* merge p and next */
            NextSlot(p) = NextSlot(next);
            NextFree(p) = NextFree(next);
        }
    }
    if (prev)
    {
        NX_ASSERT((char *)NextSlot(prev) <= p);
        if (NextSlot(prev) == p)
        {		/* merge prev and p */
            NextSlot(prev) = NextSlot(p);
            NextFree(prev) = NextFree(p);
        }
    }
}
